\documentclass[submission]{FPSAC2017}

\articlenumber{43}
\addbibresource{43_Duchi_Guerrini_Rinaldi_Schaeffer.bib}


\usepackage[utf8]{inputenc}
\usepackage{mathtools}

\newtheorem{thm}{Theorem}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{pro}[thm]{Proposition}
\newtheorem{con}[thm]{Conjecture}

\crefname{thm}{Theorem}{Theorems}

\newcommand{\cP}{\ensuremath{\mathcal{P}}}
\newcommand{\cT}{\ensuremath{\mathcal{T}}}
\newcommand{\Bs}{\beta}
\newcommand{\Bu}{B}
\newcommand{\Ps}{\pi}
\newcommand{\Pu}{P}
\newcommand{\Ds}{\delta}
\newcommand{\Du}{D}
\newcommand{\Ts}{\tau}
\newcommand{\Tu}{T}

\title[Fighting Fish: enumerative properties]{Fighting Fish:
  enumerative properties}

\author[Duchi, Guerrini, Rinaldi and Schaeffer]{Enrica Duchi%\thanks{boo} 
\addressmark{1}, Veronica Guerrini\addressmark{2}, Simone Rinaldi\addressmark{2} \and Gilles Schaeffer\addressmark{3}}

\address{\addressmark{1}IRIF, Universit\'e Paris Diderot, Paris, France\\ 
\addressmark{2}Università di Siena, Siena, Italy\\
\addressmark{3}LIX, CNRS, \'Ecole Polytechnique, Palaiseau, France\\
}

\received{\today}

\abstract{Fighting fish were very recently introduced by the authors
  as combinatorial structures made of square tiles that form two
  dimensional branching surfaces. A main feature of these fighting fish is
  that the area of uniform random fish of size $n$ scales like
  $n^{5/4}$ as opposed to the typical $n^{3/2}$ area behavior of the
  staircase or directed convex polyominoes that they generalize.

  In this extended abstract we focus on enumerative properties
  of fighting fish: in particular we provide a new decomposition and
  we show that the number of fighting fish with $i$ left lower free
  edges and $j$ right lower free edges is equal to
  \begin{equation*}
  \frac{(2i+j-2)!(2j+i-2)!}{i!j!(2i-1)!(2j-1)!}.
  \end{equation*}
  These numbers are known to count rooted planar non-separable maps
  with $i+1$ vertices and $j+1$ faces, or two-stack-sortable
  permutations with respect to ascending and descending runs, or left
  ternary trees with respect to vertices with even and odd abscissa.
  However we have been unable until now to provide any explicit bijection
  between our fish and such structures. Instead we provide new refined
  generating functions for left ternary trees to prove further
  equidistribution results.  }

\keywords{enumerative combinatorics, exact formulas, algebraic generating functions}


\begin{document}

\maketitle

\section{Introduction}

In a recent paper \cite{fighting-fish} we introduced a new family of
combinatorial structures which we call {\em fighting fish} since they
are inspired by the aquatic creatures known under the same name (see
\href{https://fr.wikipedia.org/wiki/Combattant}{this page on Betta Splendens fish}).  The easiest
description of fighting fish is that they are built by gluing together
unit squares of cloth along their edges in a directed way that
generalize the iterative construction of directed convex polyominoes
\cite{tony}.

\begin{figure}
\begin{center}
\includegraphics[scale=0.8]{square}
\end{center}
\caption{The three ways to grow a fish by adding a cell.}
\label{fig:IterativeConstruction}
\end{figure}

More precisely, we consider 45 degree tilted unit squares which we
call \emph{cells}, and we call the four edges of these cells
\emph{left upper edge}, \emph{left lower edge}, \emph{right upper
  edge} and \emph{right lower edge} respectively. We view a cell as a
simple surface with a (square) boundary, and we intend to create
larger and larger surfaces by gluing cells along edges.  We call
\emph{free} an edge of a cell which it is not glued to an edge of
another cell. All fighting fish are then obtained from an initial cell
called the \emph{head} by attaching cells one by one in one of the
three following ways: (see \cref{fig:IterativeConstruction})
\begin{itemize}
\item Let $a$ be a cell already in the fish whose right upper
  edge is free; then glue the left lower edge of a new cell $b$ to the
  right upper edge of $a$.

\item Let $a$ be a cell already in the fish whose right lower
  edge is free; then glue the left upper edge of a new cell $b$ to the
  right lower edge of $a$.

\item Let $a$, $b$ and $c$ be three cells already in the fish and such
  that $b$ (respectively $c$) has its left lower (respectively upper) edge glued to
  the right upper (respectively lower) side of $a$, and $b$ (respectively $c$) has
  its right lower (respectively right upper) edge free; then simultaneously
  glue the left upper and lower edges of a new cell $d$ respectively to
  the right lower edge of $b$ and to the right upper edge of $c$.
\end{itemize}
Observe that in the first two cases the new cell is attached to the
existing fish by one edge only (see also \cref{fig:fish1}(c)), while in
the second case the cell is attached by two edges.

While this description is iterative we are interested in the objects
that are produced, independently of the order in which cells are
added: a \emph{fighting fish} is a surface formed of collection of
cells glued together that \emph{can} be obtained by the
iterative process above. The \emph{head} of the fighting fish is the
only cell with two free left edges, its \emph{nose} is the leftmost
point of the head; a \emph{final cell} is a cell with two free right
edges, and the corresponding \emph{tail} is its rightmost point; the
\emph{fin} is the path that starts from the nose of the fish, follows
its border counterclockwise, and ends at the first tail it meets (see
\cref{fig:fish1}(a)).


The \emph{size} of a fighting fish is the number of lower free  edges
(which is also equal to the number of upper free
edges). Moreover, the \emph{left size} (respectively \emph{right size}) of a
fighting fish is its number of left lower free edges (respectively right
lower free edges). Clearly, the left and right size of a fish sum to its size.
The \emph{area} of a fighting fish is the number of its cells.



\medskip

Examples of fighting fish are parallelogram polyominoes (aka staircase
polyominoes), directed convex polyominoes, and more generally simply
connected directed polyominoes in the sense of \cite{tony}. However,
one should stress the fact that fighting fish are not necessarily
polyominoes because cells can be adjacent without being glued together
and more generally cells are not constrained to fit in the plane and
can cover each other, as illustrated by \cref{fig:fish1}(a)
and~\ref{fig:fish1}(d).  The two smallest fighting fish which are not
polyominoes have size 5 and area 4: as illustrated by
\cref{fig:fish1}(c), they are obtained by gluing a square $a$ to
the upper right edge of the head, a square $b$ to the right lower edge
of the head and either a square $c$ to the right lower edge of $a$, or
a square $d$ to the upper right edge of $b$.  The smallest fighting
fish not fitting in the plane has size 6 and area 5, it is obtained by
gluing both $c$ to $a$ and $d$ to $b$: in the natural projection of
this fighting fish onto the plane, squares $c$ and $d$ have the same
image. Observe that we do not specify whether $c$ is above or below
$d$; rather we consider that the surface has a branch point at vertex
$c\cap d$ (see \cref{fig:fish1}(d)).

\begin{figure}
\begin{center}
\includegraphics[scale=0.7]{fishpr}
\end{center}
\caption{(a) A fighting fish which is not a polyomino; (b) A
  parallelogram polyomino; (c) The two fighting fish with area 4 and
  size 5 that are not polyominoes; (d) Two different representations
  of the unique fighting fish with area 5 and size 6 not fitting in
  the plane.}
\label{fig:fish1}
\end{figure}

\medskip
In \cite{fighting-fish} we obtained the generating functions of fighting
fish using essentially Temperley's approach, that is, a decomposition
in vertical slices. This allowed us to prove:
\begin{thm}[\cite{fighting-fish}]\label{thm:fighting-fish}
The number of fighting fish with $n+1$ lower free edges is 
\begin{equation}
\frac{2}{(n+1)(2n+1)}{3n\choose n}.
\end{equation}
\end{thm} 
We showed moreover that the average area of fighting fish of size $n$
is of order $n^{5/4}$.  This behavior suggests that, although fighting
fish are natural generalizations of directed convex polyominoes, they
belong to a different universality class: indeed the order of
magnitude of the area of most classes of convex polyominoes is 
$n^{3/2}$ instead \cite{richard}.

In the present extended abstract we explore further the remarkable
enumerative properties of fighting fish. We propose in
\cref{sec:deco} a new decomposition that extends to fighting
fish the classical wasp-waist decomposition of polyominoes
\cite{MBMinTony}.  Using the resulting equation we compute in
\cref{sec:gfP1} the generating functions of fighting fish with
respect to the numbers of left and right lower free edges, fin length and
number of tails, and use the resulting explicit parametrization to
prove the following bivariate extension of
\cref{thm:fighting-fish}:
\begin{thm}\label{thm:count}
The number of fighting fish with $i$ left lower free edges and $j$ right
lower free edges is
\begin{equation}\label{for:for1}
\frac{(2i+j-2)!(2j+i-2)!}{i!j!(2i-1)!(2j-1)!}
=\frac1{ij}{2i+j-2\choose j-1}{2j+i-2\choose i-1}.
\end{equation}
\end{thm}
We also discuss in \cref{sec:marked} several remarkable
relations between fighting fish with marked points of various
types. In particular we prove:
\begin{thm}\label{thm:marked}
The number of fighting fish with $i$ left lower free and $j$ right lower free
edges with a marked tail is
\begin{equation}\label{for:for2}
\frac{(2i+2j-3)}{(2i-1)(2j-1)}{2i+j-3\choose j-1}{2j+i-3\choose i-1}.
\end{equation}
\end{thm}
All these results confirm the apparently close relation of fighting
fish to the well studied combinatorial structures known as \emph{non
  separable planar maps} \cite{B}, \emph{two stack sortable
  permutations} \cite{Zeilb,west,bona}, and \emph{left ternary trees}
\cite{DDP,JS}.  The closest link appears to be between fighting fish
and left ternary trees, that is, ternary trees whose vertices all have
non negative abscissa in the natural embedding \cite{kuba}. We prove in
\cref{sec:ternary} the following theorem, which was conjectured
in \cite{fighting-fish}:
\begin{thm}\label{thm:fin-core}
The number of fighting fish with size $n$ and fin length $k$ is equal
to the number of left ternary trees with $n$ nodes, $k$ of which are
accessible from the root using only left and middle branches.
\end{thm}
We prove this theorem by an independent computation of the generating
functions of left ternary trees with respect to $n$ and $k$ (see
\cref{thm:generalizedKuba}), building on Di Francesco's method
\cite{diFrancesco2} for counting positively labeled trees.  As
discussed in \cref{sec:ternary} we conjecture that
\cref{thm:fin-core} extends to take into account the left and
right size and the number of tails but the computation of the generating
functions of left ternary trees according to these parameters appears to be harder and we have only been able to prove
this bijectively in the case of fighting fish with at most two tails,
and in the case of fighting fish with $h$ tails but at most $h+2$
lower edges that are not in the fin.

\section{A wasp-waist decomposition}\label{sec:deco}

\begin{thm}\label{thm:wasp-waist}
Let $P$ be a fighting fish. Then exactly one of the following cases (A), (B1), (B2), (C1), (C2) or (C3) occurs:
\begin{description}
\item{(A)} $P$ consists of a single cell;
\item{(B)} $P$ is obtained from a smaller size fighting fish $P_1$:
\begin{description}
\item{(B1)} by gluing the right lower edge of a new cell to the upper
  left edge of the head of $P_1$ (\cref{fig:waist_fish}~(B1));
\item{(B2)} by gluing every left edge of the fin of $P_1$ to the upper
  right edge of a new cell, and gluing the left upper edge of every new
  cell to the right lower edge of the cell immediately on the left of
  its top vertex (\cref{fig:waist_fish}~(B2));
\end{description}
\item{(C)} $P$ is obtained from two smaller size fighting fish, $P_1$ and $P_2$:
\begin{description}
\item{(C1)} by performing on $P_1$ the operation described in~(B2) and
  then gluing the upper left edge of the head of $P_2$ to the last
  edge of the fin of $P_1$ (\cref{fig:waist_fish}~(C1));
\item{(C2)} by choosing a right edge $r$ on the fin of $P_1$ (last
  edge of the fin excluded) and gluing every left edge preceding $r$
  on the fin to the upper right edge of a new cell and, as above,
  gluing the left upper edge of every new
  cell to the right lower edge of the cell immediately on the left of
  its top vertex;
  Then, gluing the upper left edge of the head of
  $P_2$ to $r$ (\cref{fig:waist_fish}~(C2));
\item{(C3)} by choosing a left edge $\ell$ on the fin of $P_1$ and
  gluing every left edge of the fish fin preceding $\ell$ (included)
  to the upper right edge of a new cell and, as above, gluing the left
  upper edge of every new cell to the right lower edge of the cell
  immediately on the left of its top vertex; Then, gluing the upper
  left edge of the head of $P_2$ to the right lower edge of the cell
  glued to $\ell$ (\cref{fig:waist_fish}~(C3)).
\end{description}
\end{description}
Moreover each of the previous operations, when applied to arbitrary fighting fish $P_1$ and if necessary $P_2$, produces a fighting fish. 
\end{thm}
\begin{figure}
\centering
\includegraphics[width=1\textwidth]{waist_fish}
\caption{The wasp-waist decomposition.}
\label{fig:waist_fish}
\end{figure}

Observe that Cases (A), (B1) and (B2) could have been alternatively
considered as degenerate cases of Case (C1) where $P_1$ or $P_2$ would
be allowed to be empty. Similarly Case (C1) and (C2) could have been
merged into a unique case but we distinguish the two because in Case
(C1) the first tail of $P_1$ is lost in the operation.  Staircase
polyominoes are exactly the fighting fish obtained using only Cases
(A), (B1), (B2) and (C1).

\begin{proof} Omitted (see \cite{fighting-fish2}).
\end{proof}

Let $P(t,y,a,b,u)=\sum_{P} t^{\mathrm{size} (P)-1} y^{\mathrm{tails}
  (P)-1} a^{\mathrm{rsize} (P)-1} b^{\mathrm{lsize} (P)-1}
u^{\mathrm{fin} (P)-1}$ denote the generating functions of fighting fish
with variables $t,y,a,b$ and $u$ marking the size, the
number of tails, the right size, the left size, the fin length, all
decreased by one. The variable $t$ is redundant in view of variables
$a$ and $b$ but it will be convenient to keep it.

\begin{cor}\label{cor:gf} 
The generating functions $\Pu(u)\equiv \Pu(t,y,a,b,u)$
of 
fighting fish satisfies
the equation
\begin{equation}\label{eqn:eq0}
\Pu(u)=tu(1+a\Pu(u))(1+b\Pu(u))+ytabu\Pu(u)\frac{\Pu(1)-\Pu(u)}{1-u}.
\end{equation}
\end{cor}
\begin{proof} This is a direct consequence of the previous theorem (see \cite{fighting-fish2}).
\end{proof}

\section{Enumerative results for fish}\label{sec:count}
\subsection{The algebraic solution of the functional equation}\label{sec:gfP1}
The equation satisfied by fighting fish is a combinatorially founded
polynomial equation with one catalytic variable: this class of
equations was thoroughly studied by Bousquet-M\'elou and Jehanne
\cite{MBMA} who proved that they have algebraic solutions.
\begin{thm}\label{thm:gfP1}
Let $\Bs\equiv \Bs(t,y,a,b)$ denote the unique power series solution of the equation
\begin{equation}\label{eqn:eq6U}
\Bs=t\left(1+y\frac{ab\Bs^2}{1-ab\Bs^2}\right)^2(1+a\Bs)(1+b\Bs).
\end{equation}
Then the generating function $\Pu(1)\equiv \Pu(t,y,a,b,1)$ of fighting fish can be expressed as 
\begin{equation}\label{eqn:eq8U}
\Pu(1)=\Bs-\frac{yab\Bs^3(1+a\Bs)(1+b\Bs)}{(1-ab\Bs^2)^2}.
\end{equation}
\end{thm}
This theorem easily implies \cref{thm:count} using Lagrange
inversion (see \cite{fighting-fish2}).
\begin{proof}[Proof of \cref{thm:gfP1}]
Our proof follows closely the approach of \cite{MBMA}, so we omit the
details (see \cite{fighting-fish2}) and only present the
strategy: Rewrite Equation~\eqref{eqn:eq0} as
\begin{equation}\label{eqn:eq1}
(u-1)\Pu(u)=tu(u-1)(1+a\Pu(u))(1+b\Pu(u))+ytuab\Pu(u)(\Pu(u)-\Pu(1)).
\end{equation}
and take the derivative with respect to $u$:
\begin{align*}
\MoveEqLeft
\Pu(u)-t(2u-1)(1+a\Pu(u))(1+b\Pu(u))-ytab\Pu(u)(\Pu(u)-\Pu(1)) \\
&=-\frac{\partial}{\partial u}\Pu(u)\cdot \big(u-1-tu(u-1)(a+b+2ab\Pu(u))-ytuab(2\Pu(u)-\Pu(1))\big)
\end{align*}
Now there clearly exists a power series $U$ that cancels the
second factor in the right hand side of the previous equation: $U$ is
the unique power series root of the equation
\begin{equation}\label{eqn:eq2U}
U-1=tU(U-1)(a+b+2ab\Pu(U))+ytabU(2\Pu(U)-\Pu(1)).
\end{equation}
The series $U$ must also cancel the left hand side,
\begin{equation}\label{eqn:eq3U}
\Pu(U)=t(2U-1)(1+a\Pu(U))(1+b\Pu(U))+ytab\Pu(U)(\Pu(U)-\Pu(1)), 
\end{equation}
and, for $u=U$, Equation~\eqref{eqn:eq1} reads
\begin{equation}\label{eqn:eq1U}
(U-1)\Pu(U)=tU(U-1)(1+a\Pu(U))(1+b\Pu(U))+ytUab\Pu(U)(\Pu(U)-\Pu(1)).
\end{equation}
Solving the resulting system of 3 equations for the three unknowns 
$U$, $\Pu(U)$ and $\Pu(1)$ yields the theorem, with $\Pu(U)=\Bs$.
\end{proof}

The full series $\Pu(u)$ is clearly algebraic of degree at most 2 over
$\mathbb{Q}(y,a,b,u,\Bs)$, but it admits in fact a parametrization directly
extending the one of the theorem. 
\begin{cor}\label{cor:Pu}
Let $\Bu(u)\equiv \Bu(t,y,a,b,u)$ be the unique power series
solution of the equation:
\begin{equation}\label{eqn:Pu}
\Bu(u)=tu\left(1+a\Bu(u)+ya\Bu(u)\frac{b\Bs(1+a\Bs)}{1-ab\Bs^2}\right)
\left(1+b\Bu(u)+yb\Bu(u)\frac{a\Bs(1+b\Bs)}{1-ab\Bs^2}\right),
\end{equation}
so that $\Bu(1)=\Bs$ as defined in \cref{thm:gfP1}, then
\begin{equation*}
\Pu(u)=\Bu(u)
-yab\Bu(u)^2\Bs\frac{(1+a\Bs)(1+b\Bs)(1-ab\Bs^2+yab\Bs^2)}
{(1-ab\Bs^2)^2(1-ab\Bu(u)\Bs+yab\Bu(u)\Bs)}.
\end{equation*}
\end{cor}

\subsection{Fighting fish with marked points}\label{sec:marked}
\begin{figure}
\centering
\includegraphics[width=0.8\textwidth]{marked_fish}
\caption{Fish with marked points: (a) a tail, (b) a branch point, (c) an upper flat point.}
\label{fig:markedpoints}
\end{figure}

Among the vertices on the boundary of a fish we already distinguished
the nose and the tails: these are the only vertices of the boundary
having no cells neither right above nor right below them. As
illustrated by \cref{fig:markedpoints}, let us further call
\emph{branch point} a vertex of the boundary having cells of the fish
both right above and right below it, and \emph{upper (respectively lower)
  flat point} a vertex of the boundary having a cell right below but
not right above (respectively right above but not right below). Let $P^<$
denote the generating functions of fish with a marked branch point, $P^>$
the generating functions of fish with a marked tail, $2P^{-}$ the
generating functions of fish with a marked \emph{flat} point, that is, a
marked point which is neither the head nor a tail nor a branch point
(observe that each fish has the same number of upper and lower flat
points, hence the factor 2). The generating functions of fighting fish
with a marked point is then:
\begin{equation}
\Pu(1)+2P^{-}+P^>+P^<=2\frac{t\partial}{\partial t}(t\Pu(1)).
\end{equation}

From the fact that there is always one more tail than branch point we have
\begin{equation}
\Pu(1)+P^<=P^>
\end{equation}
so that we also have 
\begin{equation}
P^-+P^>=\Pu(1)+P^<+P^-=\frac{t\partial}{\partial t}(t\Pu(1)).
\end{equation}
Fighting fish with a marked branch point or tail can also be counted thanks to the variable $y$:
\begin{equation}
P^<=\frac{y\partial}{\partial y}\Pu(1), \quad\textrm{ or }\quad 
P^>=\frac{y\partial}{\partial y}(y\Pu(1)).
\end{equation}

Observe that differentiating Equation~\eqref{eqn:eq1} with respect to $y$
instead of $u$ yields the same coefficient for the derivative of
$\Pu(u)$, which cancels for $u=U$. This simplification leads to 
the remarkable relations:
\begin{equation}\label{eq:markedPU}
P^<=y\frac{\partial}{\partial y} \Pu(1)=\Pu(U)-\Pu(1),
\quad\textrm{ and }\quad
P^>=\Pu(U).
\end{equation}
The latter relation allows us to use bivariate Lagrange inversion on the
parametrization $\Pu(U)=\Bs$ in \cref{thm:gfP1} to prove
\cref{thm:marked}, we omit the details (see \cite{fighting-fish2}).

Similarly differentiating Equation~\eqref{eqn:eq1} with respect to $t$ and taking $u=U$ yields:
\begin{equation}\label{eq:eqU}
U=\frac1{1-V} \quad\textrm{ where }\quad V=ytab\frac{t\partial}{\partial t} \Pu(1)=ytab(P^-+P^<).
\end{equation}

Equations~\eqref{eq:markedPU} and~\eqref{eq:eqU} admit direct combinatorial
interpretations (see \cite{fighting-fish2}).



\section{Fighting fish and left ternary trees: the fin/core relation}\label{sec:ternary}

A \emph{ternary tree} is a finite tree which is either empty or
contains a root and three disjoint ternary trees called the left,
middle and right subtrees of the root. Given an initial root label $j$,
a ternary tree can be naturally embedded in the plane in a
deterministic way: the root has abscissa $j$ and the left
(respectively middle, right) child of a node with abscissa $i\in\mathbb{Z}$
has abscissa $i+1$ (resp, $i$, $i-1$). A \emph{$j$-positive tree} is a
ternary tree whose nodes all have non negative abscissa in the
latter embedding; $0$-positive trees were first introduced in the
literature with the name \emph{left ternary tree} \cite{DDP,JS} (in
order to be consistent with these papers one should orient the abscissa
axis toward the left).

It is known that the number of left ternary trees with $i$ nodes at
even position and $j$ nodes at odd position is given by
Formula~\eqref{for:for1} \cite{DDP,JS}. In order to refine this result
we introduce the following new parameters on left ternary trees:
\begin{itemize}
\item Let the \emph{core} of a ternary tree $T$ be the largest
  subtree including the root of $T$ and consisting only of left and
  middle edges. 
\item Let a \emph{right branch} of a ternary tree be a maximal
  sequence of right edges.
\end{itemize}
In order to prove \cref{thm:fin-core} we compute the generating
functions of $j$-positive trees according to the number of nodes and
nodes in the core.

\subsection{A refined enumeration of $j$-positive trees}

Let $\Ds\equiv \Bs(t,1,1,1)$ be the specialization of the unique power series
solution of Equation~\eqref{eqn:eq6U} for $y=a=b=1$, so that
\begin{align*}
  \Ds=\frac t{(1-\Ds)^2}.
\end{align*}
Let furthermore $\Ts\equiv \Ts(t)=1/(1-\Ds)$ and $X\equiv X(t)$ be the unique formal power series solution of the equation
\begin{align*}
X=(1+X+X^2)\Ds.
\end{align*}
The series $\Ts$ satisfies $\Ts=1+t\Ts^3$, it is thus a generating function of ternary trees.

Building on Di Francesco's educated guess and check approach
\cite{diFrancesco2}, Kuba obtained a formula for the generating
functions of $j$-positive trees:
\begin{thm}[\cite{diFrancesco2,kuba}] \label{thm:kuba}
The generating functions $\Ts_j\equiv \Ts_j(t)$ of $j$-positive trees with respect to the number of nodes is given for all $j\geq0$
by the explicit expression:
\begin{equation*}
\Ts_j=\Ts\frac{(1-X^{j+5})(1-X^{j+2})}{(1-X^{j+4})(1-X^{j+3})}.
\end{equation*}
\end{thm}
Now the generating function of ternary trees is easily refined to take into account the number of nodes in the core: let
\begin{align*}
\Tu(u)&=1+tu\Tu(u)^2\Ts\quad\textrm{ and }\quad
\Du(u)=tu\Tu(u)^2,
\end{align*}
where $\Tu(1)=\Ts$ and a comparison with the specialization of
Equation~\eqref{eqn:Pu} for $y=a=b=1$ shows that
$\Du(u)\equiv\Bu(t,1,1,1,u)$.
In particular the generating function
of fighting fish according to the size and the fin length, given by
\cref{cor:Pu}, can be written as
\begin{align}\label{eqn:eqPuTu}
\Pu(u)&=\Du(u)-\Du(u)^2\frac{\Ds}{(1-\Ds)^2}
=\Tu(u)(1+\Ds)-\Tu(u)^2\Ds-1.
\end{align}

\begin{thm} \label{thm:generalizedKuba}
The generating functions $\Tu_j(u)\equiv \Tu_j(t,u)$ of $j$-positive trees with respect to the number of nodes and size of the core is given for $j\geq-1$ by
\begin{align}\label{eq:generalizedKuba} 
\Tu_j(u)&=\Tu(u)\frac{H_j(u)}{H_{j-1}(u)}\frac{1-X^{j+2}}{1-X^{j+3}}
\end{align}
where for all $j\geq-2$, 
\begin{align*}
H_j(u)&=(1-X^{j+1})X\Tu(u)-(1+X)(1-X^{j+2}).
\end{align*}
\end{thm}
\cref{thm:generalizedKuba}, together with \cref{cor:Pu} as rewritten above, directly implies \cref{thm:fin-core}.
\begin{proof}[Proof of \cref{thm:fin-core}]
We want to show that $\Tu_0(u)=1+\Pu(u)$: we have
\begin{align*}
\Tu_0(u)&=\Tu(u)\frac{H_0(u)}{H_{-1}(u)}\frac{1-X^{2}}{1-X^{3}},
\end{align*}
and by definition $H_{-1}=-(1+X)(1-X)$ and $H_{-2}(u)=(X-1)\Tu(u)$,
so that
\begin{align*}
\Tu_0(u)&=\Tu(u)\frac{(1-X)X\Tu(u)-(1+X)(1-X^2)}{-(1-X^2)}\frac{1-X^{2}}{1-X^{3}}
=-\Tu(u)^2\Bs+\Tu(u)(1+\Bs),
\end{align*}
which coincides with Equation~\eqref{eqn:eqPuTu} up to a constant term for the empty tree.
\end{proof}

\begin{proof}[Proof of \cref{thm:generalizedKuba}]
In order to prove the theorem it is sufficient to show that the series
given by the right hand side of Equation~\eqref{eq:generalizedKuba} satisfies for all $j\geq -1$ the
equation:
\begin{equation}\label{eq:rectrees}
\Tu_{j}(u)=1+tu\Tu_{j+1}(u)\Tu_{j}(u) \Ts_{j-1}
\end{equation}
where $\Ts_j$ is given by \cref{thm:kuba}, with the convention
that $\Ts_{-2}=0$: indeed the system of Equations~\eqref{eq:rectrees}
clearly admits the generating functions of $j$-positive ternary trees as
its unique power series solutions.
%
The case $j=-1$ is immediate:
\begin{equation*}
\Tu_{-1}(u)=\Tu(u)\frac{H_{-1}(u)}{H_{-2}(u)}\frac{1-X}{1-X^2}=1.
\end{equation*}
Let now $j\geq0$, then the right hand side of Equation~\eqref{eq:rectrees} reads
\begin{align}\nonumber
1+&tu\Tu(u)^2\Ts\cdot\frac{H_{j+1}(u)}{H_{j-1}(u)}\cdot
\frac{1-X^{j+4}}{1-X^{j+3}}\cdot\frac{1-X^{j+1}}{1-X^{j+4}}\\&
=\frac{H_{j-1}(u)(1-X^{j+3})+(\Tu(u)-1)H_{j+1}(u)(1-X^{j+1})}{H_{j-1}(u)(1-X^{j+3})}\label{eqn:lhs}
\end{align}
and we want to show that this is equal to the right hand side of Equation~\eqref{eq:generalizedKuba}.
Now
{\small
\begin{align*}
H_{j-1}(u)(1-X^{j+3})
&=(1-X^{j+3})(1-X^{j})X\Tu(u)-(1+X)(1-X^{j+1})(1-X^{j+3}),\\
-H_{j+1}(u)(1-X^{j+1})
&=-(1-X^{j+1})(1-X^{j+2})X\Tu(u)+(1+X)(1-X^{j+3})(1-X^{j+1}),\\
\Tu(u)H_{j+1}(u)(1-X^{j+1})&=(1-X^{j+1})(1-X^{j+2})X\Tu(u)^2-(1+X)(1-X^{j+3})(1-X^{j+1})\Tu(u),
\end{align*}
}
while
\begin{align*}
\Tu(u)H_j(u)(1-X^{j+2})
&=(1-X^{j+2})(1-X^{j+1})X\Tu(u)^2-(1+X)(1-X^{j+2})^2\Tu(u).
\end{align*}
The coefficients of $\Tu(u)^2$ and $\Tu(u)^0$ in the numerators
of~\eqref{eqn:lhs} and of~\eqref{eq:generalizedKuba} are clearly matching. Upon
expanding all contributions to the coefficient of $\Tu(u)$ in these
numerators in powers of $X$, the various terms are  seen to
match as well.
\end{proof}

\subsection{A refined conjecture}
In view of \cref{thm:count} and \cref{thm:fin-core}, it
is natural to look for a common generalization. Indeed one can even
take the number of tails into account:
\begin{con}\label{fin-core}
The number of fighting fish with size $n$, fin length $k$, having $h$
tails, with $i$ left lower free edges and $j$ right lower free edges
is equal to the number of left ternary trees with $n$ nodes, core size
$k$, having $h$ right branches, with $i+1$ non root nodes with even
abscissa and $j$ nodes with odd abscissa.
\end{con}
This conjecture naturally calls for a bijective proof, however we have
been unable until now to provide such a proof, except in two specific
cases:
The case of left ternary trees with at most one right branch, which are in bijection with fighting fish with at most two tails for all values of $n$, $k$, $i$ and $j$,
and the case of left ternary trees with $h$ right branches and at
  most $h+2$ vertices not in the core, which are in bijection with
  fighting fish with $h$ tails and $h+2$ lower edges that are not in
  the fin.


\acknowledgements{The first and last author are grateful to the
  University of Siena where part of this work was done. The anonymous
  referees are thanked for their careful reading and useful comments.}

\begingroup\emergencystretch=5em
\printbibliography
\endgroup
\end{document}
\newpage
\appendix


\begin{figure}
\centering
\includegraphics[width=0.4\textwidth]{fishpict}
\caption{A real fighting fish.}
\label{fig:ff}
\end{figure}

\section{Proof of \cref{thm:wasp-waist} and \cref{cor:gf}}\label{ap:deco}
\begin{proof}[Proof of the theorem]
The operations described in \cref{thm:wasp-waist} produce valid
fighting fish: indeed given incremental growths of $P_1$ and $P_2$ we
obtain a valid incremental growth of $P$ upon starting from the new
head, growing the head of $P_1$ interleaving the next steps of the
growth of $P_1$ with insertions of the new cells: each new cell is to
be inserted just before the fin cell it will be attached to; when this
is done, the head of the fish $P_2$ can be attached on $P_1$ and the
rest of $P_2$ growth from there.

It thus remains  to show that every fighting fish of size greater
that $2$ can be uniquely obtained by applying one of the operations
$(B)$ or $(C)$ to fish of smaller size.

In order to prove the result let us describe how to decompose a fish
$P$ which is not reduced to a cell. In order to do this we need two
further definition: First let us call \emph{cut edge} of $P$ any
common side $e$ of two cells of $P$ such that cutting $P$ along $e$
yields two connected components. Second let the set of \emph{fin
  cells} of $P$ be the set of cells incident to a left edge of the
fin: the head of $P$ is always a fin cell and the other fin cells have
non-free left upper sides (since their left lower sides are free and
they must be attached by a left side).

Now the decomposition is as follows: 
\begin{itemize}
\item First mark the head of $P$ as \emph{removable} and consider the
  other fin cells iteratively from left to right: mark them as
  \emph{removable} as long as their left upper side is not a cut edge
  of $P$. Let $R(P)$ be the set of removable cells of $P$.
\item If all fin cells are marked as removable then removing these
  cells yields a fighting fish $P_1=P\setminus R(P)$, and applying the
  construction of Case (B2) to $P_1$ gives $P$ back. Conversely any
  fish produced as in Case (B2) has all its fin cells removable.
\item Otherwise let $c$ be the first fin cell which is not
  removable. Upon cutting the left upper side $e$ of $c$, two
  components are obtained: let $P_2$ be the component containing $c$
  and let $\bar P_1$ be the other component, which contains by
  construction all the removable cells of $P$. Using the incremental
  construction of fighting fish one easily check that $P_1=\bar
  P_1\setminus R(P)$ is a (possibly empty) fighting fish, and $P_2$ is
  a non-empty fighting fish.
\begin{itemize}
\item If $P_1$ is empty then applying the construction of Case (B2) to
  $P_1$ yields $P$ back, and conversely all fish produced as in Case
  (B2) have a decomposition with $P_1$ empty.
\item Otherwise the edge $e$ corresponds to a right lower side $\bar
  e_1$ on the fin of $\bar P_1$, or equivalently to an edge $e_1$ of
  the fin of $P_1$: if $\bar e_1$ is a side of a removable cell of $P$
  then $e_1$ is the right upper edge of this cell, which is a right
  lower edge on the fin of $P_1$ (this corresponds to Case (C3));
  otherwise $e_1=e$ is a right lower edge on the fin of $P_1$ (this
  corresponds to Case (C1) or (C2) depending whether $e_1$ is the
  rightmost edge on the fin of $P_1$ or not.
\end{itemize}
\end{itemize}
\end{proof}



\begin{proof}[Proof of the corollary] The wasp-waist decomposition of \cref{thm:wasp-waist}
is readily translated into the following functional equation:
\begin{align*}
P(u) &= tu + tub P(u) + tua P(u) + tuab P(u)^2 + \\
&  ytabP(u) \sum_{P_1} t^{\mathrm{size} (P_1)-1} y^{\mathrm{tails} (P_1)-1} a^{\mathrm{rsize} (P_1)-1} 
b^{\mathrm{lsize} (P_1)-1} \left( u+\ldots +u^{\mathrm{fin} (P_1)-1} \right )\\
&= tu(1+aP(u))(1+bP(u))+ytabuP(u)\frac{P(1)-P(u)}{1-u},
\end{align*}
where the only difficult point is to observe that given a pair
$(P_1,P_2)$ of non empty fighting fish with $\mathrm{fin}(P_1)=k+1$,
Cases~(C2) and~(C3) together produce $k$ fighting fish with fin size
$2$, $3$, \dots, $k+1$ respectively.
\end{proof}
\section{Proof of \cref{thm:gfP1}}\label{ap:gf}
Let us resume the proof from the system formed by Equations~\eqref{eqn:eq1U}, \eqref{eqn:eq2U} and~\eqref{eqn:eq3U}.

Comparing Equation~\eqref{eqn:eq1U} and Equation~\eqref{eqn:eq3U}
multiplied by $U$ we immediately deduce the simpler relation
\begin{equation}\label{eqn:eq4U}
P(U)=tU^2(1+aP(U))(1+bP(U)).
\end{equation}
Now comparing Equation~\eqref{eqn:eq1U} and Equation~\eqref{eqn:eq2U}
multiplied by $P(U)$ yields, up to canceling a factor $tU$,
\begin{equation*}
(U-1)(1+(a+b)P(U)+abP(U)^2)=(U-1)P(U)(a+b+2abP(U))+yabP(U)^2,
\end{equation*}
that is
\begin{equation}\label{eqn:eq5U}
U=1+y\frac{abP(U)^2}{1-abP(U)^2}
\end{equation}
In view of Equations~\eqref{eqn:eq4U} and~\eqref{eqn:eq5U}, $P(U)$ is the unique formal power series solution of the equation:
\begin{equation}\label{eqn:eq6U_2}
P(U)=t\left(1+y\frac{abP(U)^2}{1-abP(U)^2}\right)^2(1+aP(U))(1+bP(U)).
\end{equation}
In other terms $P(U)=B$ as defined in \cref{thm:gfP1}.  Now using
Equation~\eqref{eqn:eq5U} to eliminate $U$ in
Equation~\eqref{eqn:eq1U}, and canceling a factor $yabP(U)$ we have:
\begin{equation*}
\frac{P(U)^2}{1-abP(U)^2}
=tU\frac{P(U)}{1-abP(U)^2}
(1+aP(U))(1+bP(U))+tU(P(U)-P(1)).
\end{equation*}
Using Equation~\eqref{eqn:eq4U} to expand a factor $P(U)$ in the left
hand side, and canceling a factor $tU$, this equation can be
rewritten as:
\begin{equation}\label{eqn:eq}
\frac{P(U)U(1+aP(U))(1+bP(U))}{1-abP(U)^2}
=\frac{P(U)}{1-abP(U)^2}
(1+aP(U))(1+bP(U))+(P(U)-P(1)).
\end{equation}
In other words:
\begin{equation*}
P(U)-P(1)=(U-1)
\frac{P(U)(1+aP(U))(1+bP(U))}{1-abP(U)^2}
\end{equation*}
and using again Equation~\eqref{eqn:eq4U},
\begin{equation}\label{eqn:eq7U}
P(U)-P(1)=
\frac{yabP(U)^3(1+aP(U))(1+bP(U))}{(1-abP(U)^2)^2}.
\end{equation}
Finally
\begin{equation}\label{eqn:eq8U_2}
P(1)=P(U)-
\frac{yabP(U)^3(1+aP(U))(1+bP(U))}{(1-abP(U)^2)^2},
\end{equation}
which concludes the proof of the theorem using $P(U)=B$.

\section{Proof of the bivariate formulas}\label{ap:lagrange}
\textbf{In this proof we implicitly set $y=1$ in all series.}
\cref{thm:count,thm:marked} can be derived by
bivariate Lagrange inversion on the expression of $P(1)$ in terms of
the series
\begin{align*}
\bar R=\frac{aB(1+bB)}{1-abB^2}\qquad\textrm{and}\qquad
\bar S=\frac{bB(1+aB)}{1-abB^2}.
\end{align*}
Indeed 
\begin{equation}\label{eq:B-RS}
B=t\frac{(1+aB)(1+bB)}{(1-abS^2)^2}=t(1+\bar R)(1+\bar S),
\end{equation}
so that $\bar R$ and $\bar S$ satisfy
\begin{align}\label{eq:bivarlarg}
\begin{cases}
\bar R&=ta(1+\bar R)(1+\bar S)^2\\
\bar S&=tb(1+\bar R)^2(1+\bar S).
\end{cases}
\end{align}
Indeed Equation~\eqref{eqn:eq8U} then rewrites as
\begin{align}\label{eq:P1-RS}
P(1)&=B-abB^3\frac{(1+aB)(1+bB)}{(1-abB^2)^2}
=t(1+\bar R)(1+\bar S)(1-\bar R\bar S).
\end{align}
Given a system $\{A_1=a_1\Phi_1(A_1,A_2),A_2=a_2\Phi_2(A_1,A_2)\}$ the bivariate Lagrange inversion theorem states that for any function $F(x_1,x_2)$, 
\begin{align*}
[a_1^{n_1}a_2^{n_2}]F(A_1,A_2)=\frac1{n_1n_2}
[x_1^{n_1-1}x_2^{n_2-1}]&\left(
\frac{\partial^2 F(x_1,x_2)}{\partial x_1\partial x_2}\Phi_1(x_1,x_2)^{n_1}
\Phi_2(x_1,x_2)^{n_2}\right.\\
&+\frac{\partial F(x_1,x_2)}{\partial x_1}\frac{\partial \Phi_1(x_1,x_2)^{n_1}}{\partial x_2}\Phi_2(x_1,x_2)^{n_2}\\
&\left.+\frac{\partial F(x_1,x_2)}{\partial x_2}\frac{\partial \Phi_2(x_1,x_2)^{n_2}}{\partial x_1}\Phi_1(x_1,x_2)^{n_1}\right)
\end{align*}
In other words, \begin{equation}\nonumber
[a_1^{n_1}a_2^{n_2}]F(A_1,A_2)=\frac1{n_1n_2}
[x_1^{n_1-1}x_2^{n_2-1}]\Phi_1(x_1,x_2)^{n_1}
\Phi_2(x_1,x_2)^{n_2} H,\mbox{ where}\end{equation} \begin{equation}\nonumber
H=\frac{\partial^2 F(x_1,x_2)}{\partial x_1\partial x_2}
+{n_1}\frac{\partial F(x_1,x_2)}{\partial x_1}\frac{\partial \Phi_1(x_1,x_2)}{\partial x_2}\frac{1}{\Phi_1(x_1,x_2)}+{n_2}\frac{\partial F(x_1,x_2)}{\partial x_2}\frac{\partial \Phi_2(x_1,x_2)}{\partial x_1}\frac{1}{\Phi_2(x_1,x_2)}.\end{equation}



Setting $t=1$ and applying the bivariate Lagrange inversion formula to the function
$B(\bar R,\bar S)$ in Equation~\eqref{eq:B-RS}, where $\bar R=a\Phi_1(\bar R,\bar
S)$ and $\bar S=b\Phi_2(\bar R,\bar S)$ as defined in system~\eqref{eq:bivarlarg}, yields
\begin{align*}
[a^{i-1}b^{j-1}]B&=\frac{1}{(i-1)(j-1)}
[\bar R^{i-2}\bar S^{j-2}]\left((1+\bar R)^{i+2j-3}(1+\bar
S)^{2i+j-3}(2i+2j-3)\right)\\
&=\frac{(2i+2j-3)}{(i-1)(j-1)}\binom{2j+i-3}{i-2}\binom{2i+j-3}{j-2}\\
&=\frac{(2i+2j-3)}{(2i-1)(2j-1)}\binom{2j+i-3}{i-1}\binom{2i+j-3}{j-1}.
\end{align*}
This proves \cref{thm:marked}.
Now, apply the bivariate Lagrange inversion formula to the function $P(1)$ in
Equation~\eqref{eq:P1-RS}: 
it holds
\begin{align*}
[a^{i-1}b^{j-1}]P(1)=\frac{1}{(i-1)(j-1)}
[\bar R^{i-2}\bar S^{j-2}]\left((1+\bar R)^{i+2j-3}(1+\bar
S)^{2i+j-3}\right.&(-4+4\bar R\bar S\\
&+2i(1-2\bar R\bar S-\bar S)\\
&\left.+2j(1-2\bar R\bar S-\bar R))\right).
\end{align*}
By extracting coefficients of $\bar R^{i-2}\bar S^{j-2}$ yields
\begin{align*}
[a^{i-1}b^{j-1}]P(1)=\frac{1}{(i-1)(j-1)}&\left(2(i+j-2)\binom{2j+i-3}{i-2}\binom{2i+j-3}{j-2}\right.\\
&-4(i+j-1)\binom{2j+i-3}{i-3}\binom{2i+j-3}{j-3}\\
&\left.-2j\binom{2j+i-3}{i-3}\binom{2i+j-3}{j-2}-2i\binom{2j+i-3}{i-2}\binom{2j+i-3}{j-3}\right).
\end{align*}
Manipulating and summing all the binomial coefficients it results
\begin{equation}\nonumber
[a^{i-1}b^{j-1}]P(1)=\frac1{ij}\binom{2j+i-2}{i-1}\binom{2i+j-2}{j-1}.
\end{equation}


\section{Bijective interpretations}\label{ap:bijections}
\subsection{A bijective proof of the relation $P^>=P(U)$}
\begin{pro}
There is a bijection between 
\begin{itemize}
\item fighting fish with a marked tail having $i+1$ left lower free edges
  and $j+1$ right lower free edges,
\item and pairs $(P,S)$ where $P$ is a fighting fish with fin size
  $k+1$ and $S$ is a $k$-tuple $(U_1,\ldots,U_k)$ of sequences
  $U_i=(V_{i,1},\ldots,V_{i,j_i})$ of fish that are marked on an upper
  flat point or a branch point, such that the total number of left
  lower free edges and right lower free edges are respectively $i+1$ and $j+1$.
\end{itemize}
\end{pro}
The bijection is illustrated by \cref{fig:compose}.
\begin{figure}
\centering
\includegraphics[width=0.8\textwidth]{composition}
\caption{The bijective interpretation of $P^>=P(U)$.}
\label{fig:compose}
\end{figure}
\begin{proof}[Sketch of proof] 
Given a pair $(P,S)$ as above, mark the first tail of $P$, then slice
$P$ above each inner point of its fin, cut each $V_{i,j}$ at its nose
and marked point and inflate it vertically to match the width of $P$
above the $i$th point $x_i$ of its fin, and insert the inflated
sequence $U_i$ between the slice before and after $x_i$. This produce
a fighting fish $P'$ with a marked tail.  The fact that the marked
point of each $V_{i,j}$ is an upper flat point or a branch point ensures
that the resulting point in $P'$ is a branch point. 

Conversely a fish $P'$ with a marked tail can be decomposed upon
traveling along the \emph{spine} connecting the tail to the nose and
cutting the fish in slices: Starting from the tail, 
\begin{enumerate}
\item travel to the left along the current lower free edge to reach a point $x$
\item if $x$ is a flat point then a new slice of $P$ is obtained above
  the edge that has been traversed; resume at step 1;
\item otherwise $x$ is a branch point, then let $\ell$ denote the
  length of the shortest vertical cut above $x$ that separates the
  nose and the tail:
\begin{enumerate}
\item travel along the spine until the length of the vertical cut
  returns to the the value $\ell$ for the first time, above a new
  lower point $x$: the resulting slice gives the next factor $V_{i,j}$
  in the decomposition;
\item if the new point $x$ is again a branch point then resume at the
  previous step,
\item otherwise $x$ is a lower flat point and a new factor $U_i$ has been completed; resume at step 1.
\end{enumerate} 
\end{enumerate}
The proof that the two constructions above are inverse one of the
other is omitted.
\end{proof}

\subsection{A bijective proof of the relation $V=ytab(\Delta P)(U)$}
Let $(\Delta P)(u)=u\frac{P(u)-P(1)}{u-1}=P(u^k\to u+\ldots+u^k)$.
Then $(\Delta P)(u)$ is the generating series of fighting fish with
a marked edge on the fin, where $u$ marks the distance between the
nose and the endpoint of the marked edge.

\begin{pro}
There is a bijection between 
\begin{itemize}
\item fighting fish with a marked branch or flat lower point having
  $i+1$ left lower free edges and $j+1$ right lower free edges,
\item and pairs $(P,S)$ where $P$ is a fighting fish with a marked
  edge on the fin at distance $k$ from the nose and $S$ is a $k$-tuple
  $(U_1,\ldots,U_k)$ of sequences $U_i=(V_{i,1},\ldots,V_{i,j_i})$ of
  fish that are marked on an upper flat point or a branch point, such
  that the total number of left lower free edges and right lower free edges are
  respectively $i+1$ and $j+1$.
\end{itemize}
\end{pro}
\begin{proof}[Sketch of proof]
This bijection is based on the same decomposition as the previous one.
The only difference is that the substitution of $U$ factors is not
made along the whole fin of the fish: as a result the marked point is
a flat lower point or a branch point instead of being a tail.
\end{proof}
\subsection{A bijective proof of the relation $ytabP^<=V^2$}
\begin{pro}
There is a bijection between
\begin{itemize}
\item fighting fish a marked branch point having $i+1$ left lower free edges and $j+1$ right lower free edges,
\item and pairs of fighting fish $(P_1,P_2)$ marked on a branch or lower flat point, such that the total number of left lower free edges and right lower free edges are
  respectively $i+1$ and $j+1$.
\end{itemize}
\end{pro}
The bijection is illustrated by \cref{fig:branch}.
\begin{figure}
\centering
\includegraphics[width=0.8\textwidth]{branch}
\caption{The bijective interpretation of $ytabP^<=V^2=(ytab(P^-+P^<))^2$.}
\label{fig:branch}
\end{figure}
\begin{proof}
Let $P$ be a fighting fish with a marked branch point $x$, and let
$\ell$ denote the length of the shortest vertical cut segment above
$x$. Then the decomposition is obtained by cutting $P$ at this vertical
cut segment and at the first vertical cut segment of the same length
that is found along the spine from $x$ toward the nose of $P$. 
\end{proof}
\subsection{A bijective proof of the relation $P^>=tU^2(1+aP^>)(1+bP^>)$}
This relation follows from the wasp-waist decomposition of fighting
fish upon substituting $u=U$: the relation $P^>=P(U)$ and
$ytabU(\Delta P)(U)=V$ indeed immediately leads to
$P^>=tU(1+aP^>)(1+bP^>)+VP^>$, from which one concludes by iteration.


\end{document}

\section{The colored parametrization}



Let $R=aP(U)$ and $S=bP(U)$, so that $(R,S)$ is the unique formal power series pair solution of the system
\begin{equation*}
\begin{cases}
R&=at\left(1+y\frac{RS}{1-RS}\right)^2(1+R)(1+S)\\
S&=bt\left(1+y\frac{RS}{1-RS}\right)^2(1+R)(1+S)
\end{cases}
\end{equation*}
Then
\begin{equation*}
ab(P(U)-P(1))=
\frac{yaRS^2(1+R)(1+S)}{(1-RS)^2}
\end{equation*}
and
\begin{equation*}
abP(1)=aS-yaS\frac{RS(1+R)(1+S)}{(1-RS)^2}
\end{equation*}



\subsection{Proof of the refined conjecture}
Let us consider the following system of equations:
\begin{equation*}
\begin{cases}
R&=at\left(1+y\frac{RS}{1-RS}\right)^2(1+R)(1+S)\\
&=at\left(1+R+y(RS+RSR+RSRS+RSRSR+RSRSRS+\cdots)\right)
\left(1+S+y(SR+SRS+SRSR+SRSRS+SRSRSR+\cdots)\right)\\
S&=bt\left(1+y\frac{RS}{1-RS}\right)^2(1+R)(1+S)
\end{cases}
\end{equation*}
Then $R$ and $S$ are respectively the generating series of possibly empty ternary
trees with a black or white root vertex without right child.  The generating series
$\bar R$ and $\bar S$ of ternary trees with a black or white root
vertex are then
\begin{equation*}
\begin{cases}
\bar R&=\left(1+y\frac{RS}{1-RS}\right)(1+R)=1+R+yRS+yRSR+yRSRS+\ldots\\
\bar S&=\left(1+y\frac{SR}{1-RS}\right)(1+S)=1+S+ySR+ySRS+ySRSR+\ldots
\end{cases}
\end{equation*}
The generating series of left ternary trees is then, according to the full conjecture
\begin{equation*}
S_0 =S-yS\frac{R(1+S)}{1-SR}\frac{S(1+R)}{1-RS}.
\end{equation*}
However it is not that easy to write the equation for $R_i$ and $S_i$ taking $y$ into account!



With colors:
\begin{align*}
R(u)&=atu\left(1+R(u)+yR(u)(S+SR+SRS+\ldots\right)
\left(1+S(u)+yS(u)(R+RS+RSR+\ldots\right)\\
&=atu\left(1+R(u)+yR(u)\frac{S+SR}{1-SR}\right)
\left(1+S(u)+yS(u)\frac{R+RS}{1-RS}\right)\\
S(u)&=btu\left(1+R(u)+yR(u)(S+SR+SRS+\ldots\right)
\left(1+S(u)+yS(u)(R+RS+RSR+\ldots\right)\\
&=btu\left(1+R(u)+yR(u)\frac{S+SR}{1-SR}\right)
\left(1+S(u)+yS(u)\frac{R+RS}{1-RS}\right)\\
\end{align*}

\end{document}

The infinite family $T_j(u)$ satisfies a simple system of equation that
follows immediately from the standard recursive decomposition of trees
at their root vertex: For all $k\geq0$, let $\varepsilon_{2k}=a$ and
$\varepsilon_{2k+1}=b$, and let $(B_j(u))_{j\geq0}$,
$(T_j(u))_{j\geq0}$ and $(T_j^*)_{j\geq -1}$ be the unique family of
formal power series determined by the equations
\begin{equation*}
B_j(u)=tuT_{j+1}(u)T_j(u), \quad\textrm{ and }\quad
T^*_j=\varepsilon_jB_j(1)\cdot(1+T^*_{j-1}),
\end{equation*}
for all $j\geq0$, 
with the convention that $T^*_{-1}=0$, and 
\begin{equation*}
T_j(u)=1+\varepsilon_jB_j(u)+y\varepsilon_jB_j(u)T^*_{j-1}.
\end{equation*}
for all $j\geq0$. The series $\varepsilon_jB_j(u)$ can be interpreted
as the generating series of trees of $\cT_j$ without a right edge at
the root vertex, while $T^*_j$ is the generating series of non-empty
right subtrees of the root of trees of $\cT_{j+1}$ (or equivalently
they are trees of $\cT_{j}$ in which the root right branch does not
contribute to a factor $y$ and the core is not taken into
account). 

\subsection{A composition equation}
Let $\bar T(u)\equiv \bar T(t,y,a_0,a_{1},a,b;u)$ be the generating series of
nonempty left ternary trees, where $u$ (respectively $t,y$) takes account of
the core size (respectively the size, the number of right branches) of a left
ternary tree, and $a_0$ (resp $a_{1}$) of the number of non root nodes
in abscissa $0$ that are middle (respectively right) children, and $a$
(respectively $b$) of the number of nodes in nonzero even abscissa (respectively odd
abscissa).  Then, we provide a system of functional equations
satisfied by the generating series $T(u)$:
\begin{align}\label{LTT}
\bar T(u)&=tu\left(1+a_0\bar T(u)\right)\left(1+b\bar T^*\right),\\
\label{T*}
T^*&=T\left(t,y,b(1+a_{1}yT(1)),b(1+a_{1}T(1)),b,a;u\right)(1+a_{1}yT(1)).
\end{align}
Indeed, according to \eqref{LTT} a left ternary tree is made of a root,
which gives the contribute $tu$, joined both to a (possibly empty) left
ternary tree as its middle subtree giving factor $1+a_0T(u)$ and to a
(possibly empty) particular ternary tree as its left subtree, whose nodes
all have abscissa lower than or equal to $1$, that is defined in~\eqref{T*}
and gives the contribute $1+bT^*$. Equation~\eqref{T*}  can be combinatorially
interpreted as taking a left ternary tree and joining each node in abscissa
$0$ (root included) to a possibly empty right left ternary subtree. Note
that if the right subtree is joined to a right node there are no contributes to $y$.

Using \textsc{Maple} we verified \cref{fin-core} for the first
terms of the series expansions of $P(t,y,a,b;u)$ and $T(t,y,a,a,a,b;u)$.


\subsection{Small right branches}
In the search of a proof of \cref{fin-core} we were able to
give bijection that transport all parameters in two special cases:



